#include <bits/stdc++.h>
using namespace std;
void Merge(int Array[],int TempArray[],int left,int right,int middle)
{
    int i,j,index1,index2;
    //将数组存放到临时数组
    for(j = left;j<=right;j++)
        TempArray[j] = Array[j];
    index1 = left;
    index2 = middle+1;
    i = left;
    while(index1<=middle&&index2<=right)
    {
        if(TempArray[index1]<=TempArray[index2])
            Array[i++] = TempArray[index1++];
        else
            Array[i++] = TempArray[index2++];
    }
    while(index1<=middle)
        Array[i++] = TempArray[index1++];
    while(index2<=right)
        Array[i++] = TempArray[index2++];
}
void MergeSort(int Array[],int TempArray[],int left,int right)
{
    //Array为待排序的数组，left,right为两端
    int middle;
    if(left<right)//序列中只有0或者1个记录，不用排序
    {
        middle = (left+right)/2;//平分为两个子序列
        MergeSort(Array,TempArray,left,middle);//对左半边排序
        MergeSort(Array,TempArray,middle+1,right);//对右半边排序
        Merge(Array,TempArray,left,right,middle);//归并
    }
}
int main() {
    int a[] = {1,9,2,7,5,6,8,4,3};
    int b[9] = {1};
    MergeSort(a,b,0,9);
    for(int i=0;i<9;i++)
        cout<<a[i]<<" ";
    return 0;
}